Masala #0928

Qulmamat Liplandiya shahriga sayohatga bordi. Bu shaxarda $1$ dan $n$ gacha raqamlangan shaxarlar mavjud bo'lib, ikkita shaxarni bog'lovchi yo'l bir tomonlama edi. Qulmamatning $T$ soat vaqti mavjud bo'lib, u $T$ soat ichida imkon qadar ko'proq shaxarlarga sayohatni amalga oshirishni istaydi.

Qulmamat $1$ shaxardan sayohatni boshlab $n$ shaxarda yakunlamoqchi. Agar ikki shaxarni bog'lab turuvchi yo'l $(u_i, v_i)$ mavjud bo'lsa bu yo'lni u $t_i$ soatda bosib o'tadi.

Sizning vazifangiz Qulmamat imkon qadar ko'proq shaxarlarga sayohat qilishi uchun $T$ soatdan oshmagan vaqtda ketma-ket qaysi shaxarlarga borish kerak ekanligini ko'rsatuvchi dastur tuzib berishdan iborat.

Dastlabki satrda $n,m,T(2\leq n\leq 10000, 1\leq m\leq 10000, 1\leq T\leq 10^6)$ sonlar, mos ravishda shaxarlar soni, yo'llar soni va sayohat uchun Qulmamatda mavjud bo'lgan vaqt.

Kiyingi $m$ ta satrda $u_i, v_i, t_i(1\leq u_i, v_i\leq n, 1\leq t_i\leq 10^9)$ uchliklar, bu yerda $(u, v)$ juflik o'rtasida yo'l mavjud va bu yo'lni bosib o'tish uchun $t$ vaqt ketadi. 

Chiqish faylining dastlabki satrida Qulmamat jami nechta shaxarlarga sayohat qilishini va kiyingi satrda sayohatni qaysi shaxarlarda amalga oshirishi kerak ekanligini ketma-ket probil bilan ajratilgan holda chop eting. Agar bunday yechimlar bir nechta bo'lsa istalganini chop etishingiz mumkun.